1053E - Euler tour - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define gg puts("no"),exit(0)
#define N 1000010
int n,m,a[N],pr[N],sf[N],nt[N],nw=1,c[N],vi[N];
void dl(int x,int y){
sf[pr[x]]=sf[y];
pr[sf[y]]=pr[x];
}
int gt(){
while(vi[nw])nw++;
if(nw>n)gg;
vi[nw]=1;
return nw;
}
void dfs(int l,int r){
if((r-l)&1)gg;
for(int i=l;i<=r;i=sf[i])
while(nt[i]){
if(nt[i]>r)gg;
dfs(sf[i],pr[nt[i]]);
dl(sf[i],nt[i]);
nt[i]=nt[nt[i]];
}
int s=0,ct=0,rt=a[pr[l]];
for(int i=l;i<=r;i=sf[i]){
s++;
ct+=a[i]>0;
}
s=(s+1)/2;
if(ct>s)gg;
for(int i=sf[l];i<=r;i=sf[i])
if(!a[i]&&ct<s)a[i]=gt(),ct++;
if(s==1&&!ct)a[l]=gt();
for(int i=l;sf[i]<=r;i=sf[i]){
while(i>l&&sf[i]<=r&&!a[pr[i]]&&a[i]&&a[sf[i]]){
a[pr[i]]=a[sf[i]];
dl(i,sf[i]);
i=pr[pr[i]];
}
while(i>=l&&sf[sf[i]]<=r&&a[i]&&a[sf[i]]&&!a[sf[sf[i]]]){
a[sf[sf[i]]]=a[i];
dl(sf[i],sf[sf[i]]);
i=pr[i];
}
}
for(int i=l;i<=r;i=sf[i])
if(!a[i])a[i]=rt;
}
int main(){
cin>>n;
m=n*2-1;
for(int i=1;i<=m;i++){
cin>>a[i];
c[a[i]]++;
}
if(a[1]&&a[m]&&a[1]!=a[m])gg;
a[1]=a[m]=a[1]|a[m];
for(int i=0;i<=m;i++){
pr[i]=i-1;
sf[i]=i+1;
}
for(int i=m;i;i--)
if(a[i]){
nt[i]=vi[a[i]];
vi[a[i]]=i;
}
dfs(1,m);
puts("yes");
for(int i=1;i<=m;i++)
printf("%d ",a[i]);
puts("");
return 0;
}